package heap
import (
	"common"
	"fmt"
)

type Heap struct {
	Pq []int
	N int
}

func (h *Heap)IsEmpty() bool {
	return h.N == 0
}

func (h *Heap)Size() int {
	return h.N
}

func (h *Heap)Insert(v int)  {
	h.N++
	h.Pq[h.N] = v
	h.swim(h.N)
}

func (h *Heap)DelMax() int {
	max := h.Pq[1]
	common.Exch(h.Pq, 1, h.N)
	h.N--
	h.sink(1)
	return max
}

func (h *Heap)swim(k int)  {
	for k > 1 && h.Pq[k/2] < h.Pq[k] {
		common.Exch(h.Pq, k/2, k)
		k = k/2
	}
}

func (h *Heap)sink(k int)  {
	for 2*k <= h.N {
		j := int(2*k)
		if j < h.N && h.Pq[j] < h.Pq[j+1] {
			j++
		}
		if h.Pq[k] >= h.Pq[j] {
			break
		}
		common.Exch(h.Pq, k, j)
		k = j
	}
}

func (h *Heap)Print()  {
	fmt.Println(h.Pq[1:h.N+1])
}


func sink(k int)  {
	for 2*k <= h.N {
		j := int(2*k)
		if j < h.N && h.Pq[j] < h.Pq[j+1] {
			j++
		}
		if h.Pq[k] >= h.Pq[j] {
			break
		}
		common.Exch(h.Pq, k, j)
		k = j
	}
}
